package week02

import (
	"strconv"
	"strings"
)

// 297. 二叉树的序列化与反序列化
// https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

type Codec struct {}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	ans := this.marshal(root, []string{})
	return strings.Join(ans, " ")
}

func (this *Codec) marshal(root *TreeNode, ans []string) []string {
	if root == nil {
		ans = append(ans, "nil")
		return ans
	}
	ans = append(ans, strconv.FormatInt(int64(root.Val), 10))
	ans = this.marshal(root.Left, ans)
	ans = this.marshal(root.Right, ans)
	return ans
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	var vals = strings.Split(data, " ")
	var root, _ = this.unmarshal(vals)
	return root
}

func (this *Codec) unmarshal(val []string) (*TreeNode, []string) {
	if len(val) == 0 {
		return nil, nil
	}
	if val[0] == "nil" {
		return nil, val[1:]
	}
	var node = &TreeNode{}
	i, _ := strconv.Atoi(val[0])
	node.Val = i
	val = val[1:]
	node.Left, val = this.unmarshal(val)
	node.Right, val = this.unmarshal(val)
	return node, val
}

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}